package Sort;

import java.util.Arrays;

public class HeapSort {

  public static void main(String[] args) {
    int[] arr = new int[]{4,6,8,5,9};
    heapSort(arr);
  }

  public static void heapSort(int[] arr){
    System.out.println("堆排序！！！");
    int temp = 0;
//    adjustHeap(arr,1,arr.length);
//    System.out.println("第一次排序：" + Arrays.toString(arr));//4 9 8 5 6
//
//    adjustHeap(arr,0,arr.length);
//    System.out.println("第二次排序：" + Arrays.toString(arr));//9 6 8 5 4
    for (int i = arr.length/2 - 1; i >= 0; i--) {
      adjustHeap(arr,i,arr.length);
    }

    for (int j = arr.length - 1; j > 0 ; j--) {
      //交换
      temp = arr[j];
      arr[j] = arr[0];
      arr[0] = temp;
      adjustHeap(arr,0,j);
    }

    System.out.println("排序后的结果" + Arrays.toString(arr));
  }

  /*
  arr待调整的数组
  i表示非叶子结点在数组中素引
  length表示对多少个元素继续调整
   */
//  将一个数组（二叉树）调整为大顶堆
  public static void adjustHeap(int[]arr,int i,int length){
    /*

       4
     6   8
   5  9

     */
    int temp = arr[i];

    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {

      if (k + 1 < length && arr[k] < arr[k + 1]){//说明左子节点小于右子节点
        k++;
      }
      if (arr[k] > temp){//如果右子节点大于temp，上移
        arr[i] = arr[k];
        i = k;
      }else {
        break;
      }
    }
    arr[i] = temp;
  }
}
